package leetcode.code;

/**
 * 给出一些不同颜色的盒子，盒子的颜色由数字表示，即不同的数字表示不同的颜色。
 * 你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k*k 个积分。
 * 当你将所有盒子都去掉之后，求你能获得的最大积分和。
 *
 * 示例 1：
 * 输入:
 *
 * [1, 3, 2, 2, 2, 3, 4, 3, 1]
 * 输出:
 *
 * 23
 * 解释:
 *
 * [1, 3, 2, 2, 2, 3, 4, 3, 1]
 * ----> [1, 3, 3, 4, 3, 1] (3*3=9 分)
 * ----> [1, 3, 3, 3, 1] (1*1=1 分)
 * ----> [1, 1] (3*3=9 分)
 * ----> [] (2*2=4 分)
 *  
 *
 * 提示：盒子的总数 n 不会超过 100。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-boxes
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class difficult_移除盒子 {


    /**
     * dp
     * 我们使用一个 dp 数组，用来存储最大分数，对于一个特定的子序列。
     * 对于元素 dp[l][r][k]，l 表示起始下标，r 表示结束下表，k 表示与第 r 个元素相似的元素个数，可以在最后一起合并并得到最终的分数存入
     * dp[l][r][k] 中。
     *
     *  例如{xl,xl+1,……xi …… xr, 6,6,6} 如果xr = 6那么 dp[l][r][[3] 表示boxes[l:r] 可得到的最大分数，同时有三个数字6 在xr之后。
     *
     */
    static class Solution {

        public int removeBoxes(int[] boxes) {
            int[][][] dp = new int[100][100][100];
            return calculatePoints(boxes, dp, 0, boxes.length - 1, 0);
        }

        public int calculatePoints(int[] boxes, int[][][] dp, int l, int r, int k) {
            if (l > r) return 0;
            if (dp[l][r][k] != 0) return dp[l][r][k];
            while (r > l && boxes[r] == boxes[r - 1]) {
                r--;
                k++;
            }
            dp[l][r][k] = calculatePoints(boxes, dp, l, r - 1, 0) + (k + 1) * (k + 1);
            for (int i = l; i < r; i++) {
                if (boxes[i] == boxes[r]) {
                    dp[l][r][k] = Math.max(dp[l][r][k], calculatePoints(boxes, dp, l, i, k + 1) + calculatePoints(boxes, dp, i + 1, r - 1, 0));
                }
            }
            return dp[l][r][k];
        }
    }

    /**
     * 执行用时 :21 ms, 在所有 Java 提交中击败了72.60%的用户
     * 内存消耗 :41 MB, 在所有 Java 提交中击败了98.65%的用户
     *
     * 令dp[i][j]表示从j开始，长度为i的字符串。
     * dp[i][j] = Math.max(dp[i-1][j] + 1, 最后一个字符与前面任意多个相同字符联合起来得分的最大值);
     * 所以对于dp，需要使用深度搜索找到 最后一个字符，与前面任意多个字符联合起来的最大得分。
     *
     * 作者：jane-73
     * 链接：https://leetcode-cn.com/problems/remove-boxes/solution/dong-tai-gui-hua-shen-du-sou-suo-by-jane-73/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    class Solution_2 {
        public int removeBoxes(int[] boxes) {
            if (boxes == null || boxes.length == 0) {
                return 0;
            }
            int n = boxes.length;
            int[][] dp = new int[n + 1][n + 1];

            for (int i = 1; i <= n; i++) {
                for (int j = 0; j <= n - i; j++) {
                    if (i == 1) {
                        dp[i][j] = 1; // 1个字符得分为1
                    } else {
                        // 深度搜索
                        dp[i][j] = Math.max(dp[i - 1][j] + 1, deepSearch(boxes, j, i + j - 1, boxes[i + j - 1], 1, dp));
                    }
                }
            }
            return dp[n][0];
        }

        private int deepSearch(int[] box, int start, int end, int cur, int count, int[][] dp) {
            int max = dp[end - start][start] + count * count;
            int preEnd = end;
            for (int i = end - 1; i >= start; i--) {
                // 连续的情况直接加
                if (box[i] == cur && box[i + 1] == cur) {
                    count++;
                    int ret = dp[i - start][start] + count * count;
                    max = Math.max(max, ret);
                    preEnd = i;
                } else if (box[i] == cur) { // 非连续的情况 需要加中间的得分
                    // 获得中间的得分
                    int ret = dp[preEnd - i - 1][i + 1];
                    // 继续深度搜索
                    ret += deepSearch(box, start, i, cur, count + 1, dp);
                    // 取最大值
                    max = Math.max(max, ret);
                }
            }
            // 返回与任意位置结合后连续得分的最大值
            return max;
        }
    }


    /**
     * 暴力法 超时
     */
    static class Solution_1 {
        public int removeBoxes(int[] boxes) {
            boolean[] removes = new boolean[boxes.length];
            return maxK(removes, boxes);
        }

        public int maxK(boolean[] removes, int[] boxes){
            int sum = 0;
            for (int i = 0; i < boxes.length; i++){
                if (!removes[i]){
                    boolean[] tmpRemoves = removes.clone();
                    int tmpSum = getKK(removes, boxes, i) + maxK(removes, boxes);
                    if (tmpSum > sum){
                        sum = tmpSum;
                        removes = tmpRemoves;
                    }else {
                        removes = tmpRemoves;
                    }
                }
            }
            return sum;
        }

        public int getKK(boolean[] removes, int[] boxes, int i){
            int j = i, k = 1;
            removes[i] = true;
            while (j++ < boxes.length-1){
                if (removes[j]) continue;
                if (!removes[j] && boxes[j]==boxes[i]){ k++; removes[j] = true;}
                else break;
            }
            j = i;
            while (j-- > 0){
                if (removes[j]) continue;
                if (!removes[j] && boxes[j]==boxes[i]) { k++; removes[j] = true;}
                else break;
            }
            return k*k;
        }
    }

    public static void main(String[] args){
        Solution s = new Solution();
        System.out.println(s.removeBoxes(new int[]{6,10,1,7,1,3,10,2,1,3}));
    }
}
